package 岛屿数目;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 判断岛屿数量
     *
     * @param grid char字符型二维数组
     * @return int整型
     */
    static int N = 210, n, m;
    static boolean[][] st = new boolean[N][N];
    static char[][] g = new char[N][N];
    static int[] dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

    public int solve(char[][] grid) {
        // write code here
        g = grid;
        n = g.length;
        m = g[0].length;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!st[i][j] && g[i][j] == '1') {
                    cnt++;
                    bfs(new PII(i, j));
                }
            }
        }
        return cnt;
    }

    private void bfs(PII start) {
        Queue<PII> q = new LinkedList<>();
        q.offer(start);
        st[start.x][start.y] = true;
        while (!q.isEmpty()) {
            PII t = q.poll();
            for (int i = 0; i < 4; i++) {
                int x = dx[i] + t.x, y = dy[i] + t.y;
                if (x < 0 || x >= n || y < 0 || y >= m) {
                    continue;
                }
                if (g[x][y] != '1') {
                    continue;
                }
                if (st[x][y]) {
                    continue;
                }
                q.offer(new PII(x, y));
                st[x][y] = true;
            }
        }
    }
}

class PII {
    int x, y;

    public PII(int x, int y) {
        this.x = x;
        this.y = y;
    }
}